1. Field
The present invention relates generally to managed runtime environments and, more specifically, to bit vector toggling for concurrent mark-sweep garbage collection.
2. Description
The function of garbage collection, i.e., automatic reclamation of computer storage, is to find data objects that are no longer in use and make their space available for reuse by running programs. Garbage collection is important to avoid unnecessary complications and subtle interactions created by explicit storage allocation, to reduce the complexity of program debugging, and thus to promote fully modular programming and increase software application portability. Because of its importance, garbage collection is becoming an integral part of managed runtime environments.
The basic functioning of a garbage collector may comprise three phases. In the first phase, all direct references to objects from currently running programs may be identified. These references are called roots, or together a root set, and a process of identifying all such references may be called root set enumeration. In the second phase, all objects reachable from the root set may be searched since these objects may be used in the future. An object that is reachable from any reference in the root set is considered a live object (a reference in the root set is a reference to a live object). An object reachable from a live object is also live. The process of finding all live objects reachable from the root set may be referred to as live object tracing (or marking and scanning). An object that is not live is considered a garbage object. In the third phase, storage space of garbage objects may be reclaimed (garbage reclamation). This phase may be conducted either by a garbage collector or by a running application (usually called a mutator). In practice, these three phases, especially the last two phases, may be functionally or temporally interleaved and a reclamation technique may be strongly dependent on a live object tracing technique.
One garbage collection technique is called mark-sweep collection. Mark-sweep garbage collectors are named for methods that implement two garbage collection phases: live object tracing and garbage reclamation. In the live object tracing phase, live objects are distinguished from garbage by tracing, that is, starting at the root set and actually traversing the graph of reachable data structures. In mark-sweep garbage collection, the objects that are reached from the root set are marked in some way, either by altering bits within the objects, or perhaps by recording them in a bitmap or some other kind of table (this process may be referred to as a marking phase). Once the live objects are marked, i.e., have been made distinguishable from the garbage objects, storage space is swept, that is, exhaustively examined, to find all of the unmarked objects (garbage) and reclaim their space. The reclaimed objects are usually linked onto one or more free lists so that they are accessible to the allocation routines. The storage space sweeping may be referred to as a sweeping phase. The sweeping phase may be conducted by a garbage collector or a mutator.
Usually, mark-sweep garbage collection cannot proceed in parallel with actual execution of mutators. All mutators may have to be stopped for a mark-sweep garbage collector to obtain a root set and to distinguish live objects from garbage (a garbage collector that stops execution of all mutators is also called a “stop-the-world” garbage collector). A garbage collection technique that stops the execution of mutators may be called a blocking garbage collection technique; otherwise, it may be called a non-blocking garbage collection technique. Obviously it is desirable to use a non-blocking garbage collection technique to decrease the disruptiveness of garbage collection in a managed runtime environment. Indeed, even if a mark-sweep garbage collector does not stop execution of any mutator, another difficulty with current mark-sweep garbage collection systems is that the marking phase for a garbage collection cycle cannot begin before the sweeping phase of the previous cycle is complete. To improve the overall performance of a managed runtime environment, it is desirable to improve not only the concurrency between mark-sweep garbage collection and execution of mutators, but the concurrency between the marking phase and the sweeping phase as well. Additionally, when there are multiple garbage collection threads, it is also desirable to increase the parallelism between different garbage collection threads.